Asynchronous transfer mode ("ATM") is a high speed communications protocol for transmitting various types of data. In an ATM network, information may be transmitted along a single line between various users of the ATM network. The users send data as a stream of individual packages commonly referred to as cells. The cells may comprise a package of data having a length of 53 bytes. In each cell, a portion of the 53 bytes may indicate the ultimate destination of that cell within the ATM network. In the language of the industry, users are connected within the ATM network via virtual circuits. In other words, a data cell may be directed to a particular user on a virtual circuit identified by a number of bits within the cell. For example, the first five bytes of a data cell indicate, among other things, the appropriate virtual circuit. Cells from the various users in the ATM network are intermixed, transmitted along the ATM network, and directed to the appropriate user of the ATM network. Because an ATM network may be a public network, each user will be able to send data or receive data at a predetermined rate, for example, ten megabits per second.
To ensure that a user does not exceed its predetermined rate of transmitting data, it may be necessary to monitor the rate at which the information is exchanged within the ATM network. At the receiving end, this monitoring may be referred to as policing a stream of events. Each virtual circuit may be checked to determine whether it is receiving information at more than the predetermined rate. At the sending end, this process may be referred to as shaping a stream of events. Shaping is just the inverse process of policing. Shaping may be implemented at a user's location to make sure that the user does not send information at more than the predetermined rate.
The ATM Forum has defined a standard by which traffic flow within an ATM network may be monitored. This standard is referred to in the industry as "the leaky bucket" function. Conceptually, the leaky bucket function provides two buckets for each virtual circuit. For example, the first bucket may measure compliance with an average data transmission rate over a fairly long time frame. The second bucket may measure compliance with a higher specified data transmission rate over a short period of time. Each bucket may be conceptualized as having a specific depth and having a hole in its bottom. The hole in the bottom controls the rate at which data flows out of the bucket to establish the predetermined data transmission rate. The depth of each bucket allows an appropriate buffer, or backlog, such that over an appropriate length of time the data transmission rate is within the prescribed limits. The first bucket may be conceptualized as being quite deep so that if data cells are transmitted at an average rate that is less than the predetermined rate, the bucket does not overflow. As for the second bucket, it may be conceptualized to be rather shallow with respect to the first bucket, thereby allowing a higher rate of data transfer over a short period of time. If a bucket overflows, the predetermined data transmission rate has been exceeded.
Several problems and drawbacks may be encountered in an attempt to implement the leaky bucket function for a large number of virtual circuits in an ATM network. First, each bucket in the ATM network may empty at a different rate. In other words, each virtual circuit may be allowed to transmit data at different predetermined rates. In this manner, a system designed to update the contents of each bucket on every clock cycle would be very costly to design and implement. Alternatively, a system designed to implement the leaky bucket function may only update the contents of a bucket when information is sent along the virtual circuit associated with that bucket. However, this technique would require a substantial amount of memory for each bucket in the ATM network. Therefore, a need has arisen for a system and method for monitoring a stream of events.